package com.huangyi;

public class Main {
    public static void main(String[] args) {
        最长回文子序列class Solution {
            public int longestPalindromeSubseq(String s) {
                char[] ch = s.toCharArray();
                int n = ch.length;
                int[][] dp = new int[n][n];

                // 从后往前遍历 i
                for(int i = n-1; i >= 0; i--){
                    // 从 i 开始往后遍历 j
                    for(int j = i; j < n; j++){
                        if(ch[i] == ch[j]){
                            if(i == j) {
                                // 单个字符
                                dp[i][j] = 1;
                            } else if (i + 1 == j) {
                                // 两个相同字符
                                dp[i][j] = 2;
                            } else {
                                // 首尾相同，加上中间部分
                                dp[i][j] = dp[i+1][j-1] + 2;
                            }
                        } else {
                            // 首尾不同，去掉首或尾取较大值
                            dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                        }
                    }
                }

                // dp[0][n-1] 就是整个字符串的最长回文子序列长度
                return dp[0][n-1];
            }
        }
    }
}